Thoạt tiên, Astoria là chiếc dẫn đầu của lớp vì được đặt lườn trước, nhưng Astoria lại được nhận số ký hiệu lườn lớn hơn so với New Orleans vì được hạ thủy trễ hơn. Lớp tàu Astoria này được đổi tên thành lớp New Orleans sau khi Astoria bị đánh chìm trong Trận chiến đảo Savo vào năm 1942. Hơn nữa, ngay sau Chiến dịch Guadalcanal, những chiếc còn lại trong lớp trải qua một đợt đại tu lớn nhằm tinh giản cho nhẹ cấu trúc thượng tầng vốn bị làm nặng thêm do việc bổ sung các hệ thống điện tử và radar mới cùng thêm nhiều vũ khí phòng không do những tiến bộ kỹ thuật. Vì vậy những con tàu này có kiểu dáng hoàn toàn mới, đáng kể là ở khu vực cầu tàu, nên được biết đến dưới tên gọi lớp New Orleans.

Astoria được đặt lườn vào ngày 1 tháng 9 năm 1930 tại Xưởng hải quân Puget Sound, được xếp lại lớp như một tàu tuần dương hạng nặng với ký hiệu lườn CA-34 vào ngày 1 tháng 7 năm 1931. Nó được hạ thủy vào ngày 16 tháng 12 năm 1933, được đỡ đầu bởi Cô Leila C. McKay (hậu duệ của Alexander McKay, thành viên của đoàn thám hiểm John Jacob Astor đã sáng lập ra Astoria, Oregon); và được đưa ra hoạt động vào ngày 28 tháng 4 năm 1934 dưới quyền chỉ huy của Thuyền trưởng, Đại tá Hải quân Edmund S. Root.